package cn.com.code.hwjs;

import java.util.Scanner;

/**
 * HJ65 查找两个字符串a,b中的最长公共子串
 * https://www.nowcoder.com/practice/181a1a71c7574266ad07f9739f791506?tpId=37&rp=1&ru=%2Fexam%2Foj%2Fta&qru=%2Fexam%2Foj%2Fta&sourceUrl=%2Fexam%2Foj%2Fta%3Fdifficulty%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tpId%3D37%26type%3D37&difficulty=3&judgeStatus=&tags=&title=&gioEnter=menu
 *
 * @author zhengpei
 * @date 2022/5/4
 */
public class Hwjs65 {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    while (sc.hasNext()) {
      String s1 = sc.nextLine();
      String s2 = sc.nextLine();
      longString(s1, s2);
    }
  }

  private static void longString(String s1, String s2) {
    String longStr = s1.length() > s2.length() ? s1 : s2;
    String shortStr = s1.length() < s2.length() ? s1 : s2;
    int shortLen = shortStr.length();
    int maxLen = 0, start = 0;
    for (int i = 0; i < shortLen; i++) {
      // 剪枝，子串长度已经不可能超过maxLen，退出循环
      if (shortLen - i + 1 <= maxLen) {
        break;
      }
      // 左指针j,右指针k,右指针逐渐向左逼近
      for (int j = i, k = shortLen; k > j; k--) {
        String subStr = shortStr.substring(i, k);
        if (longStr.contains(subStr) && maxLen < subStr.length()) {
          maxLen = subStr.length();
          start = j;
          break;
        }
      }
    }
    System.out.println(shortStr.substring(start, start + maxLen));
  }

}
